Search results for "finite [mass]"
showing 10 items of 356 documents
On Extremal Cases of Hopcroft’s Algorithm
2009
In this paper we consider the problem of minimization of deterministic finite automata (DFA) with reference to Hopcroft’s algorithm. Hopcroft’s algorithm has several degrees of freedom, so there can exist different sequences of refinements of the set of the states that lead to the final partition. We find an infinite family of binary automata for which such a process is unique. Some recent papers (cf. [3,7,1]) have been devoted to find families of automata for which Hopcroft’s algorithm has its worst execution time. They are unary automata associated to circular words. However, automata minimization can be achieved also in linear time when the alphabet has only one letter (cf. [14]), so in …
Size of Quantum Finite State Transducers
2007
Sizes of quantum and deterministic finite state transducers are compared in the case when both quantum and deterministic finite state transducers exist. The difference in size may be exponential.
Some local properties defining $\mathcal T_0$-groups and related classes of groups
2016
We call $G$ a $\operatorname{Hall}_{\mathcal X}$-group if there exists a normal nilpotent subgroup $N$ of $G$ for which $G/N'$ is an ${\mathcal X}$-group. We call $G$ a ${\mathcal T}_0$-group provided $G/\Phi(G)$ is a ${\mathcal T}$-group, that is, one in which normality is a transitive relation. We present several new local classes of groups which locally define $\operatorname{Hall}_{\mathcal X}$-groups and ${\mathcal T}_0$-groups where ${\mathcal X}\in\{ {\mathcal T},\mathcal {PT},\mathcal {PST}\}$; the classes $\mathcal {PT}$ and $\mathcal {PST}$ denote, respectively, the classes of groups in which permutability and S-permutability are transitive relations.
On Finite Satisfiability of the Guarded Fragment with Equivalence or Transitive Guards
2007
The guarded fragment of first-order logic, GF, enjoys the finite model property, so the satisfiability and the finite satisfiability problems coincide. We are concerned with two extensions of the two-variable guarded fragment that do not possess the finite model property, namely, GF2 with equivalence and GF2 with transitive guards. We prove that in both cases every finitely satisfiable formula has a model of at most double exponential size w.r.t. its length. To obtain the result we invent a strategy of building finite models that are formed from a number of multidimensional grids placed over a cylindrical surface. The construction yields a 2NEXPTIME-upper bound on the complexity of the fini…
Orlicz–Sobolev extensions and measure density condition
2010
Abstract We study the extension properties of Orlicz–Sobolev functions both in Euclidean spaces and in metric measure spaces equipped with a doubling measure. We show that a set E ⊂ R satisfying a measure density condition admits a bounded linear extension operator from the trace space W 1 , Ψ ( R n ) | E to W 1 , Ψ ( R n ) . Then we show that a domain, in which the Sobolev embedding theorem or a Poincare-type inequality holds, satisfies the measure density condition. It follows that the existence of a bounded, possibly non-linear extension operator or even the surjectivity of the trace operator implies the measure density condition and hence the existence of a bounded linear extension oper…
The Descriptive Complexity Approach to LOGCFL
1999
Building upon the known generalized-quantifier-based firstorder characterization of LOGCFL, we lay the groundwork for a deeper investigation. Specifically, we examine subclasses of LOGCFL arising from varying the arity and nesting of groupoidal quantifiers. Our work extends the elaborate theory relating monoidal quantifiers to NC1 and its subclasses. In the absence of the BIT predicate, we resolve the main issues: we show in particular that no single outermost unary groupoidal quantifier with FO can capture all the context-free languages, and we obtain the surprising result that a variant of Greibach's "hardest contextfree language" is LOGCFL-complete under quantifier-free BIT-free interpre…
Theory of tailor automata
2019
Abstract In the paper, a fragment of the new theory of tailor automata is presented, within which a deterministic finite automaton was defined. The proposed automaton provides a theoretical model of an informally characterized biomolecular automaton. The idea of working of which is founded on the concept of alternating cut of some double-stranded fragments of DNA, with the use of a restriction enzyme and ligations of some double-stranded fragments of DNA, with the use of the ligase enzyme.
Sharpness of Rickman’s Picard theorem in all dimensions
2015
We show that given \({n \geqslant 3}\), \({q \geqslant 1}\), and a finite set \({\{y_1, \ldots, y_q \}}\) in \({\mathbb{R}^n}\) there exists a quasiregular mapping \({\mathbb{R}^n\to \mathbb{R}^n}\) omitting exactly points \({y_1, \ldots, y_q}\).
Concrete syntax-based find for graphical DSLs
2020
There are services available in the most software tools we have got used to like, copy, paste, cut, find, and replace. However, the state of the art is not so good with tools of graphical languages. Even many commercial modelling tools have limited support of the find feature. We propose to add find as a service of graphical DSL tool development frameworks. This way find is available in any DSL built using the DSL tool development framework. The concrete syntax-based find has been implemented as a service of the DSL tool development framework ajoo. Two graph-based languages: UML Activity diagrams and Deterministic Finite Automata (DFA) transition diagrams are used to demonstrate usage of th…
Empirical definition of social types in the analysis of inequality of opportunity: a latent classes approach
2014
The empirical analysis of inequality of opportunity centres on disparities between social types, defined by the exposure to circumstances beyond individual control. Despite this, its main theoretical foundation—the Roemer model—does not indicate how to carry out, in practice, the required partition of the population into such types. This paper operationalises this definition of social types using a latent classes approach. Our specification is embedded in a probabilistic extension of the canonical Roemer model, which assumes that the relevant population consists of a finite number of latent types, from which each individual can be treated as a random draw. This makes possible the use of the…